package stack.柱状图中的最大矩形;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        /**
         * 每次求当前高度的最大宽度，其实就是查找下一个小于他的值
         */
        int ans = 0 ;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= heights.length; i++) {
            int currentHeight = (i == heights.length) ? 0 : heights[i];
            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]){
                int height = heights[stack.pop()];
                int width = !stack.isEmpty() ? i - stack.peek() - 1 : i;
                ans = Math.max(ans , width * height);
            }
            stack.push(i);
        }
        return ans ;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.largestRectangleArea(new int[]{2,1,6,5,6,2,3}));
    }
}
